Genetic Algorithm
Next, Genetic Algorithm is applied to this initial population of tours for a number of generations to make it 'fitter'.
Genetic Algorithm: Just like natural evolution, this has three steps - selection, recombination and mutation.
Selection
The 'fittest' members of the population get the most representation.
If we have a population of n members, we make another population of n members whose members are the same as the original population, but each member is not present exactly once.
Instead, each member of the new population is randomly sampled from the previous one, with 'fitter' members (shorter tours in this case) having higher probability of being sampled.
def roulette_wheel_selection(population, fitness_values):
"""
fitness values are the lengths of the tours, so the shorter the tour, the lower the fitness value, the higher the probability of sampling
"""
inverted_fitness = [1 / fit for fit in fitness_values]
total_fitness = sum(inverted_fitness)
selection_probabilities = [fit / total_fitness for fit in inverted_fitness]
selected_population = random.choices(population, selection_probabilities, k=len(population))
return selected_population
Recombination
The members of the new population (after selection) 'reproduce' to create a new member which has 'genes' (characteristics) of both.
Two members of the new population are randomly selected, then a certain heuristic is followed to create a new member with parts of their characteristics.
Since fitter members have higher chance of being sampled in the Selection step, there are more fitter members in the new population, and these fit members now reproduce to create new members with properties of both.
Heuristic used for creating new tours in this case is Order Crossover.
Order Crossover
Given two tours, create a new tour with the following steps:
-
Select a segment from a parent at random.
-
Produce a proto-child by copying the segment into the corresponding position of it.
-
Delete the cities which are already in the segment from the 2nd parent. The resulted sequence of citires contains the cities that the proto-child needs.
-
Place the cities into the unfixed positions of the proto-child from left to right according to the order of the sequence to produce an offspring.
Two children can be produced by taking both tours as the starting parent once.
def order_crossover(parent1, parent2):
n = len(parent1)
start, end = sorted(random.sample(range(n), 2))
segment1, segment2 = parent1[start:end + 1], parent2[start:end + 1]
child1, child2 = [-1] * n, [-1] * n
child1[start: end + 1], child2[start: end + 1] = segment2, segment1
current_idx = end + 1
for city in parent1:
if city not in segment2:
child1[current_idx % n] = city
current_idx += 1
current_idx = end + 1
for city in parent2:
if city not in segment1:
child2[current_idx % n] = city
current_idx += 1
return child1, child2
Mutation
Sometimes, with a low probability, the 'offspring' might mutate and develop new characteristics. The new tour created from the recombination process may have some changes in the tour with a given mutation probability.
Two Edge Exchange
Given a tour, randomly select two edges (connected to different pairs of cities) and swap them. This is equivalent to swapping the position of 4 cities connected by the two edges.
def two_edge_exchange(tour):
i, j, k, l = random.sample(range(len(tour)), 4)
tour[i], tour[j], tour[k], tour[l] = tour[k], tour[l], tour[i], tour[j]
return tour
Conclusion
Finally, it is checked whether the two resulting 'children' (after mutation), have better 'fitness' (shorter length) than two existing members of the population. If so, the unfittest members are replaced with the children.
This results in the overall fitness of the population increasing, albeit slightly. The entire process is carried out for a number of iterations at the end of which the population contains significantly fitter members than when starting out.